#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <cmath>
#include <exception>

#include "expr.h"

template<class T>
class Stack : public vector<T>
{
public:
    void push(const T& val){vector<T>::push_back(val);}
    T&   top() {if(vector<T>::empty()){throw ExprError("Syntax error");} return vector<T>::back();}
    void pop() {if(vector<T>::empty()){throw ExprError("Syntax error");} vector<T>::pop_back();}
};

class Operand
{
public:
    double *ref;
    double  num;
    Operand():ref(0), num(0){}
    Operand(double* r):ref(r), num(*r){}
    Operand(double  n):ref(0), num(n){}
    operator double() const {
        if (ref) {return *ref;}
        else {return num;}
    }
    operator double* const() {
        if (!ref) {throw ExprError("Not left operand");}
        return ref;
    }
};

struct OprInfo
{
    typedef void (*OprFunction)(Stack<Operand> &);
    const char* symbol;    // + - * / ...
    OprFunction eval;
    int         level;
    int         opdInc;    // Operand count increment
    int         rightAss;  // Right-associative
};
typedef const OprInfo* Operator;

#define OPERATOR_2(name, opr, level)    \
void _##name(Stack<Operand> &sNum)      \
{                                       \
    double r = sNum.top(); sNum.pop();  \
    double l = sNum.top(); sNum.pop();  \
    sNum.push(l opr r);                 \
}

#define OPERATOR_2r(name, opr, level)   \
void _##name(Stack<Operand> &sNum)      \
{                                       \
    double r = sNum.top(); sNum.pop();  \
    double &l = *sNum.top(); sNum.pop();\
    sNum.push( &(l opr r) );            \
}

#define OPERATOR_2i(name, opr, level)   \
void _##name(Stack<Operand> &sNum)      \
{                                       \
    double r = sNum.top(); sNum.pop();  \
    double l = sNum.top(); sNum.pop();  \
    sNum.push( int(l) opr int(r) );     \
}

#define OPERATOR_2ir(name, opr, level)  \
void _##name(Stack<Operand> &sNum)      \
{                                       \
    double r = sNum.top(); sNum.pop();  \
    double &l = *sNum.top(); sNum.pop();\
    int li = l;                         \
    l = li opr int(r);                  \
    sNum.push( &l );                    \
}

#define OPERATOR_1(name, opr, level)    \
void _##name(Stack<Operand> &sNum)      \
{                                       \
    double r = sNum.top(); sNum.pop();  \
    sNum.push( opr r );                 \
}

#define OPERATOR_1r(name, opr, level)   \
void _##name(Stack<Operand> &sNum)      \
{                                       \
    double &r = *sNum.top(); sNum.pop();\
    sNum.push( &(opr r) );              \
}

#define OPERATOR_1b(name, opr, level)   \
void _##name(Stack<Operand> &sNum)      \
{                                       \
    double &r = *sNum.top(); sNum.pop();\
    double t = r opr;                   \
    sNum.push( t );                     \
}

#define OPERATOR_1i(name, opr, level)   \
void _##name(Stack<Operand> &sNum)      \
{                                       \
    double r = sNum.top(); sNum.pop();  \
    sNum.push( opr int(r) );            \
}

#define OPR_FUNCTION_1(name)            \
void _##name(Stack<Operand> &sNum)      \
{                                       \
    double r = sNum.top(); sNum.pop();  \
    sNum.push( name(r) );               \
}

// define operators function
void _placeHolder(Stack<Operand> &sNum) {return;}
void _pow(Stack<Operand> &sNum) {
    double r = sNum.top(); sNum.pop();
    double l = sNum.top(); sNum.pop();
    sNum.push( pow(l, r) );
}
void _xor(Stack<Operand> &sNum) {
    double r = sNum.top(); sNum.pop();
    double l = sNum.top(); sNum.pop();
    sNum.push( int(l) ^ int(r) );
}


#include "opr.hpp"


//define operators table
#undef  OPERATOR_2
#undef  OPERATOR_2r
#undef  OPERATOR_2i
#undef  OPERATOR_2ir
#undef  OPERATOR_1i
#undef  OPERATOR_1
#undef  OPERATOR_1r
#undef  OPERATOR_1b
#undef  OPR_FUNCTION_1

#define OPERATOR_2(name, opr, level)    {#opr, _##name, level, -1, 0},
#define OPERATOR_2r(name, opr, level)   OPERATOR_2(name, opr, level)

#define OPERATOR_2i(name, opr, level)   OPERATOR_2(name, opr, level)
#define OPERATOR_2ir(name, opr, level)  OPERATOR_2(name, opr, level)
#define OPERATOR_1(name, opr, level)    {#opr, _##name, level, 0, 1},
#define OPERATOR_1r(name, opr, level)   OPERATOR_1(name, opr, level)
#define OPERATOR_1b(name, opr, level)   {#opr, _##name, level, 0, 0},
#define OPERATOR_1i(name, opr, level)   OPERATOR_1(name, opr, level)
#define OPR_FUNCTION_1(name)            {#name, _##name, 2, 0, 1},

OprInfo operatorTable[] =
{
    {";", _placeHolder, 0xFE, 0, 1},
    {"(", _placeHolder, 0xFD, 0, 0},
    {")", _placeHolder, 0xFC, 0, 0},

    {"^", _pow, 3, -1, 0},
    {"><", _xor, 10, -1, 0},
    {"xor", _xor, 10, -1, 0},

#include "opr.hpp"

    {",", _placeHolder, 16, 0, 0},
};

map<string, Operator> operators;
char cType[256] = {0};   // char types bitmap

typedef unsigned char int8;
#define CT_WSP  1
#define CT_NUM  2
#define CT_OPR  4
#define CT_SYM  8

//inline bool isHex(char c){ return (c>='0' && c<='9')||c=='.'; }
inline bool isNum(char c){ return cType[int8(c)] & CT_NUM; }
inline bool isOp(char c){  return cType[int8(c)] & CT_OPR; }
inline bool isWS(char c){  return cType[int8(c)] & CT_WSP; }// 08~0d,30
inline bool isSym(char c){ return cType[int8(c)] & CT_SYM; }
inline bool isOp(string t){return operators.find(t) != operators.end(); }

int ExprInit()
{
    for (size_t i = 0; i < sizeof(operatorTable) / sizeof(*operatorTable); i++)
    {
        operators[ operatorTable[i].symbol ] = operatorTable + i;
    }

    for (int c = 0; c < 256; c++)
    {
        if ( (c >= '0' && c <= '9') || c=='.' ) {cType[c] |= CT_NUM;}
        if ( (c >= '!' && c <= '/') || (c >= ':' && c <= '@') || (c >= '[' && c <= '^') || (c >= '{' && c <= '~') ) {cType[c] |= CT_OPR;}
        if ( (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9') || (c == '_') || (c == '[') || (c == ']') ) {cType[c] |= CT_SYM;}
        if ( c == ' ' || c == '\t' || c == '\r' || c == '\n' ) {cType[c] |= CT_WSP;}
    }
    return 0;
}

const Operator OPR_END = operatorTable + 0;    // ;
const Operator OPR_LPAR = operatorTable + 1;   // (
const Operator OPR_RPAR = operatorTable + 2;   // )
const Operator OPR_PLUS = operatorTable + 6;   // +1
const Operator OPR_MINUS = operatorTable + 7;  // -1

enum TokenType
{
    Token_NUM = 0,
    Token_OPR = 1,
    Token_SYM = 2,
    //Token_OPD = 4;
};

struct Token
{
    TokenType type;

    Operator opr;
    Operand  opd;
};

const Token TOKEN_END = {Token_OPR, OPR_END};

double stringToNum(const string& str)
{
    double ret = 0;
    stringstream ss;
    ss.str(str);
    ss >> ret;
    return ret;
}

typedef string::iterator StringItor;
void skipWhiteSpace(const string& str, StringItor& it)
{
    while( it != str.end() && isWS(*it) ){it++;}
}

double skipNumber(const string& str, StringItor& it)
{
    StringItor begin = it;
    while( it != str.end() && isNum(*it) ){it++;}
    return stringToNum(string(begin, it));
}

Operator skipOperator(const string& str, StringItor& it)
{
    StringItor begin = it++;
    string sym(begin, it);
    map<string, Operator>::iterator existOp = operators.find(sym);
    map<string, Operator>::iterator nextOp = operators.end();
    if (existOp == nextOp){return OPR_END;}
    while ( it != str.end() ) {
        it++;
        sym = string(begin, it);
        nextOp = operators.find(sym);
        if (nextOp != operators.end()) {
            existOp = nextOp;
        } else {
            it--;
            break;
        }
    }
    return existOp->second;
}

string skipSymbol(const string& str, StringItor& it)
{
    StringItor begin = it;
    while( it != str.end() && isSym(*it) ){it++;}
    return string(begin, it);
}

vector<Token> tokenize(string str, map<string, double>& vars)
{
    int numCount = 0;
    int parCount = 0;

    vector<Token> ret;
    Token token, lastToken;

    for (StringItor ptr = str.begin(); ptr != str.end();) {
        if (numCount & ~1) {throw ExprError("Operand imbalance");}
        if (parCount < 0) {throw ExprError("Parenthesis unmatch");}

        if (isWS(*ptr)) {
            skipWhiteSpace(str, ptr);
        } else if (isNum(*ptr)) {
            token.type = Token_NUM;
            token.opd = Operand(skipNumber(str, ptr));
            ret.push_back(token);
            lastToken = token;
            numCount ++;
        } else if (isOp(*ptr)) {
            token.type = Token_OPR;
            token.opr = skipOperator(str, ptr);

            if ( (token.opr->eval == _bpp || token.opr->eval == _bmm
                || token.opr->eval == _add || token.opr->eval == _sub)
                && numCount == 0) {
                token.opr -= 2;
            }

            if (lastToken.type == token.type && lastToken.opr->level == token.opr->level) {
                throw ExprError("Operator imbalance");
            }
            ret.push_back(token);
            lastToken = token;
            numCount += token.opr->opdInc;

            if (OPR_LPAR == token.opr) {parCount++;}
            if (OPR_RPAR == token.opr) {parCount--;}

            if (token.opr == OPR_END) { // check balance
                if (numCount & ~1) {throw ExprError("Operand imbalance");}
                if (parCount != 0) {throw ExprError("Parenthesis unmatch");}
                numCount = 0; //reset
            }
        } else if (isSym(*ptr)) {
            string sym = skipSymbol(str, ptr);
            if (isOp(sym)) {
                token.type = Token_OPR;
                token.opr = operators[sym];
                ret.push_back(token);
                lastToken = token;
            } else if (vars.find(sym) != vars.end()){
                token.type = Token_NUM;
                token.opd = Operand( &(vars[sym]) );
                ret.push_back(token);
                lastToken = token;
                numCount++;
            } else {
                string err = "Unrecongized symbol: ";
                err += sym;
                throw ExprError(err);
            }
        } else {
            string err = "Unrecongized symbol: ";
            err += *ptr;
            throw ExprError(err);
            ptr++;
        }
    }

    ret.push_back(TOKEN_END);

    if (numCount & ~1) {throw ExprError("Operand imbalance");}
    if (parCount != 0) {throw ExprError("Parenthesis unmatch");}

    return ret;
}

double ExprEvaluate(string exp, map<string, double>& vars)
{
    Stack<Operand> sOpd;
    Stack<Operator> sOpr;

    sOpr.push(OPR_END);

    vector<Token> tokens = tokenize(exp, vars);

    for (vector<Token>::iterator it = tokens.begin(); it != tokens.end(); it++ ) {
        if (it->type == Token_NUM) {
            sOpd.push(it->opd);
        } else if (it->type == Token_OPR) {
            if (OPR_LPAR == it->opr) {
                sOpr.push(it->opr);
            } else {
                Operator prevOp = sOpr.top();
                while ( (prevOp->level < it->opr->level) ||
                        ((prevOp->level == it->opr->level) && !it->opr->rightAss)
                        ) {
                    sOpr.pop();
                    prevOp->eval(sOpd);
                    prevOp = sOpr.top();
                }

                if (OPR_RPAR == it->opr) {
                    if (prevOp != OPR_LPAR) {throw ExprError("Parenthesis unmatch");}
                    sOpr.pop();
                } else {
                    sOpr.push(it->opr);
                }
            }
        }
    }

    if ( sOpd.size() < 1 ) {throw ExprError("Operand imbalance");}

    return sOpd.top();
}
